package offer;

import sun.misc.Unsafe;

import java.util.Scanner;
import java.util.concurrent.ConcurrentHashMap;

public class Ex36 {
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };
    private static Node rootNode;
    public static void build(int val){
        Node cur = rootNode;
        Node par = rootNode;
        while(cur!=null){
            par = cur;
            if(cur.val>=val){
                cur = cur.left;
            }
            else{
                cur = cur.right;
            }
        }
        if(par.val>=val){
            par.left = new Node(val);
        }else {
            par.right = new Node(val);
        }
    }

    public static Node treeToDoublyList(Node root) {
        if(root==null){
            return null;
        }
        Node cur = root;
        Node head =root;
        Node last =root;
        while(cur!=null){
            head = cur;
            cur=cur.left;
        }
        cur = root;
        while(cur!=null){
            last = cur;
            cur=cur.right;
        }
        dfs(root);
        head.left = last;
        last.right = head;
        return head;
    }
    public static Node dfs(Node root){
        if(root==null){
            return null;
        }
        Node cur = dfs(root.left);
        if(cur!=null){
            root.left = cur;
            cur.right = root;
        }
        cur = dfs(root.right);
        if(cur!=null){
            root.right = cur;
            cur.left = root;
            return cur;
        }
        return root;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            if(i==0){
                rootNode = new Node(scanner.nextInt());
            }else {
                build(scanner.nextInt());
            }
        }
        treeToDoublyList(rootNode);

    }
}
